package net.tp.algo.rmq;

/**
 * <p>±1 RMQ.</p>
 *
 *
 *
 *
 * @author Trung Phan
 *
 * @time $O(n)$ pre-processing time, $O(1)$ query time.
 * @space $O(n)$
 */
public class OneRMQ {


    private int[] a;
    private int n;

    private int b; // block size
    private int m; // number of blocks
    private int[] B; // the index of the min value for each block
    private int[] V; // the min value for each block
    private SparseTable st; // sparse table to lookup min block in O(1) time.

    private int[] a0; // the first element for each block.

    private int[] t; // point to lookup table
    int[][][] T; // sqrt(n) lookup tables of size m * m

    /**
     * The constructor will pre-process the data in $O(n)$ time using $O(n)$ space.
     * @param a integer array
     */
    public OneRMQ(int[] a) {

        // make sure a is ±1 array
        for (int i = 1; i < a.length; i++) {
            if (Math.abs(a[i] - a[i-1]) != 1) {
                throw new IllegalArgumentException("Not a valid ±1 array.");
            }
        }

        this.a = a;
        n = a.length;
        b = Math.max(log2(n)/2, 1);
        m = n % b == 0 ? n/b : n/b + 1;

        a0 = new int[m];
        B = new int[m];
        V = new int[m];

        for (int i = 0; i < m; i++) {
            a0[i] = a[i*b];
        }

        for (int i = 0; i < m; i++) {
            int minIndex = Math.min(i*b + b-1, n-1);
            for (int j = minIndex-1; j >= i*b; j--) {
                if (a[j] <= a[minIndex]) {
                    minIndex = j;
                }
            }
            B[i] = minIndex;
            V[i] = a[minIndex];
        }

        this.st = new SparseTable(V);

        T = new int[1<<(b-1)][b][b]; // [2^(b-1)][b-1][b-1]
        for (int i = 0; i < T.length; i++) {
            int[] s = getS(i);
            for (int p = 0; p < b; p++) {
                T[i][p][p] = p;
                for (int q = p+1; q < b; q++) {
                    if (s[T[i][p][q]] < s[T[i][p][q-1]]) {
                        T[i][p][q] = q;
                    }
                    else {
                        T[i][p][q] = T[i][p][q-1];
                    }
                }
            }
        }

        t = new int[m];
        for (int block = 0; block < m; block++) {
            t[block] = getV(block);
        }

    }

    private int[] getS(int w) {
        int[] result = new int[b]; // the number of bits are b
        for (int i = 1, mask = 1<<(b-2); i < b; i++) {
            if ( (w & mask) == 1) {
                result[i] = result[i-1]+1;
            }
            else {
                result[i] = result[i-1]-1;
            }
        }
        return result;
    }

    private int getV(int block) {
        int result = 0;
        for (int i = block * b + b-1; i > block * b; i--) {
            result <<= 1;
            if (i >= n || a[i] > a[i-1]) {
                result |= 1;
            }
        }
        return result;
    }


    /**
     *
     * @param lo lo bound (inclusive)
     * @param hi hi bound (inclusive)
     * @return the index of the min value in the range a[lo..hi] inclusive.
     */
    public int rmq(int lo, int hi) {
        if (hi < lo) throw new IllegalArgumentException();
        int bLo = getBlock(lo);
        int bHi = getBlock(hi);

        if (bLo == bHi) {
            return rmq(bLo, lo, hi);
        }

        int min1 = rmq(bLo, lo, bLo*b+b-1);
        int min2 = rmq(bHi, bHi*b, hi);

        if (bHi - bLo == 1) {
            return minIndex(min1, min2);
        }

        int minBlock = st.minIndex(bLo+1, bHi-1);
        int min3 = B[minBlock];

        return minIndex(min1, min2, min3);
    }

    private int minIndex(int i1, int i2) {
        return a[i1] <= a[i2] ? i1 : i2;
    }

    private int minIndex(int i1, int i2, int i3) {
        int result = i1;
        if (a[i2] < a[result]) result = i2;
        if (a[i3] < a[result]) result = i3;
        return result;
    }

    /**
     * Given an index i, find the block that contains this index.
     * @param i array index
     * @return block index
     */
    private int getBlock(int i) {
        return i / b;
    }

    private int rmq(int block, int lo, int hi) {
        return T[t[block]][lo-block*b][hi-block*b] + block*b;
    }



    private static int log2(int n) {
        return (int)(Math.log(n)/Math.log(2));
    }
}
